package _2022.day._002_1200_最小绝对差;

import java.util.*;

/**
 * @author： YHSimon
 * @date： 2022-07-04 22:08
 */
public class Solution {
    public List<List<Integer>> minimumAbsDifference2(int[] arr) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(arr);
        int len = arr.length;
        int minAbs = Integer.MAX_VALUE;
        for (int i = 0; i < len - 1; i++) {
            int abs = arr[i + 1] - arr[i];
            List<Integer> list = new ArrayList<>();
            list.add(arr[i]);
            list.add(arr[i + 1]);
            if (abs < minAbs) {
                ans.clear();
                ans.add(list);
                minAbs = abs;
            }
            if (abs == minAbs) {
                ans.add(list);
            }
        }
        return ans;
    }

    // 40 ms
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Map<Integer, List<List<Integer>>> map = new HashMap<>();
        Arrays.sort(arr);
        int len = arr.length;
        int minAbs = Integer.MAX_VALUE;
        for (int i = 0; i < len - 1; i++) {
            int abs = arr[i + 1] - arr[i];
            List<Integer> list = new ArrayList<>();
            list.add(arr[i]);
            list.add(arr[i + 1]);
            List<List<Integer>> tmp = map.get(abs);
            if (tmp == null) {
                tmp = new ArrayList<>();
            }
            tmp.add(list);
            map.put(abs, tmp);
            minAbs = Math.min(minAbs, abs);
        }
        return map.get(minAbs);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minimumAbsDifference(new int[]{1, 3, 6, 10, 15}));
    }
}
